package com.zlei.code.binaryTree.traversal;

import com.zlei.code.binaryTree.TreeNode;

import java.util.Stack;

/**
 * https://blog.csdn.net/qiuxinfa123/article/details/84880786
 * @Author leizhang76
 * @Date 2021/2/20 15:55
 */
public class PostOrder {

    /**
     * 递归后序遍历二叉树
     * @param node
     */
    public void post(TreeNode node){
        if (node!=null){
            post(node.left);
            post(node.right);
            System.out.println(node.val);
        }
    }

    /**
     * 后续遍历的非递归实现思路
     * 1、根节点入栈
     * 2、将根节点的左子树入栈，直到最左，没有左孩子为止
     * 3、得到栈顶元素的值，先不访问，判断栈顶元素是否存在右孩子，如果存在并且没有被访问，则将右孩子入栈，否则，就访问栈顶元素
     * @param root
     */
    public void postOrder(TreeNode root){
        if (root==null){
            return;
        }
        TreeNode tem=root;              //当前节点
        TreeNode prev=null;             //上一次访问的节点
        Stack<TreeNode> s=new Stack<>();
        while (tem!=null||!s.isEmpty()){
            //1、将根节点及其左孩子节点入栈
            while (tem!=null){
                s.push(tem);
                tem=tem.left;
            }
            if (!s.isEmpty()){
                //2、获取栈顶元素的值
                tem= s.peek();
                //3、没有右孩子，或者右孩子已经被访问过
                if (tem.right==null||tem.right==prev){
                    //则可以访问栈顶元素
                    tem=s.pop();
                    System.out.println(tem.val);
                    //标记上一次访问的节点
                    prev=tem;
                    tem=null;
                }else {
                    //存在没有被访问的右孩子
                    tem=tem.right;
                }
            }

        }

    }



}
